package com.learning.algorithm.sort.simpleSort;

import com.learning.algorithm.sort.ArraysUtil;
import com.learning.algorithm.sort.CheckSort;
import com.learning.algorithm.sort.IntArraySort;

/**
 * @Author: lishi
 * @Description: 选择排序
 * @Date: 2021/11/19 9:33
 */
public class SelectSort implements IntArraySort {
    /**
     * 简单选择排序，循环一次找一个最小数
     *
     * @param arrays
     */
    public static void selectSort(int[] arrays) {
        for (int i = 0; i < arrays.length; i++) {
            int minNums = arrays[i];
            int minPos = i;
            for (int j = i + 1; j < arrays.length; j++) {
                if (arrays[j] < minNums) {
                    minNums = arrays[j];
                    minPos = j;
                }
            }
            ArraysUtil.swap(arrays, i, minPos);
        }
    }

    /**
     * 优化选择排序，一次循环找一个最大数 一个最小数
     *
     * @param arrays
     */
    public static void selectSort2(int[] arrays) {
        //        System.out.println("原始数组 ：" + Arrays.toString(arrays));
        for (int i = 0; i < arrays.length / 2; i++) {
            //            System.out.println("===========start==============");
            int minNums = arrays[i];
            int minPos = i;
            int maxNums = arrays[i];
            int maxPos = i;
            for (int j = i + 1; j < arrays.length - i; j++) {
                if (arrays[j] < minNums) {
                    minNums = arrays[j];
                    minPos = j;
                }
                if (arrays[j] > maxNums) {
                    maxNums = arrays[j];
                    maxPos = j;
                }
            }
            if ((minPos == arrays.length - (i + 1)) && maxPos == i) {
                ArraysUtil.swap(arrays, i, minPos);
                //                System.out.println("第" + (i + 1) + "次交换最小数后的数组  ：" + Arrays.toString(arrays));
            } else if (minPos == arrays.length - (i + 1)) {
                ArraysUtil.swap(arrays, i, minPos);
                //                System.out.println("第" + (i + 1) + "次交换最小数后的数组  ：" + Arrays.toString(arrays));
                ArraysUtil.swap(arrays, arrays.length - (i + 1), maxPos);
                //                System.out.println("第" + (i + 1) + "次交换最大数后的数组  ：" + Arrays.toString(arrays));
            } else {
                ArraysUtil.swap(arrays, arrays.length - (i + 1), maxPos);
                //                System.out.println("第" + (i + 1) + "次交换最大数后的数组  ：" + Arrays.toString(arrays));
                ArraysUtil.swap(arrays, i, minPos);
                //                System.out.println("第" + (i + 1) + "次交换最小数后的数组  ：" + Arrays.toString(arrays));
            }
            //            System.out.println("===========end==============");
        }
    }

    public static void main(String[] args) {
        int arrayLength = 100000;
        int[] originArrays =  ArraysUtil.genNoDuplicateIntArray(arrayLength);
        int[] cloneArrays = new int[arrayLength];
        System.arraycopy(originArrays, 0, cloneArrays, 0, arrayLength);
        selectSort2(cloneArrays);
        System.out.println(CheckSort.checkSortResult(originArrays, cloneArrays));
    }

    public int[] sort(int[] arrays) {
        selectSort(arrays);
        return arrays;
    }

    public String getDesc() {
        return "选择排序";
    }
}
